package sort;

//快速排序
public class QuickSort {

	public static void main(String[] args) {
//		int[] a = { 25, 60, 29, 69, 35, 31, 65, 0, 1, -51, 69, -59, -35, 34,
//				25, 42, 6, 3, 59, 29, 24, 25, 25, 24, 25, 100 };
//		int[] a = { 1, 2, 3, 4, 9, 10 , 54};   //正序
//		int[] a = { 101, 92, 83, 74, 69, 60 , 54, 42}; //逆序
//		int[] a = { 10, 9, 13, 7, 12, 11 , 15, 8, 8 ,13}; //重复
		int[] a = { 5, 9, 4, 6, 3, 513, 645, 5, 1, 32, 65, 56, 123, 312, 465,
				565, -6, -88, -456, 11, 0, 0, 0, 0 };
		for (int i : a) {
			System.out.print(i + " ");
		}
		System.out.println();
//		sort(a, 0, a.length - 1);
		quickSort(a, 0, a.length - 1);
		System.out.println();
		for (int i : a) {
			System.out.print(i + " ");
		}
	}

	// 采用递归的实现思路
	public static void sort(int[] a, int left, int right) {
		if (left >= right || a == null){
			return;
		}
		int pos = partition(a, left, right); // 序列的划分操作
		System.out.println("position" + pos);
		sort(a, left, pos - 1); // 对左半部分操作
		sort(a, pos + 1, right); // 对右半部分操作
	}

	// 该函数是快速排序的核心
	public static int partition(int[] a, int left, int right) {
		if(left > right || right >= a.length || left < 0){
			return left;
		}
		int i = left, j = right - 1; // 定义初始指针的位置
		int partNum = a[right]; // 确定划分的元素为最右端元素
		while (i <= j) {
			// 自左向右查找
			while (a[i] < partNum) {
				i++;
			}
			// 只有j大于i才自右向左查找
			while (j >= i && a[j] >= partNum) {
				j--;
			}
			if (i < j) {
				// 当两个循环都退出并且i小于j的时候，即说明找到交换的值了
				MaoPaoSort.swap(a, i, j);
			}
		}
		// 最后交换a[i]和a[right]的值，right即为所选枢纽元素的位置, 将基准数归位 
		MaoPaoSort.swap(a, i, right);
		for (int l : a) {
			System.out.print(l + " ");
		}
		System.out.println(i);
		return i;
	}
	
	//这种的思想是使用parNum暂存第一个元素后然后进行原地的赋值
	public static int partition2(int[] a, int start, int end) {
		if(start > end || end >= a.length || start < 0){
			return start;
		}
		int left = start, right = end; // 定义初始指针的位置
		int partNum = a[start]; // 确定划分的元素为最右端元素
		while (left < right) {
			//right停留的位置是比parNum小的位置
			while (left < right && a[right] >= partNum){
				right--;
			}
			if (left < right) {
				a[left] = a[right];
			}
			//left停留的位置是比parNum大的位置
			while (left < right && a[left] <= partNum){
				left++;
			}
			if (left < right) {
				a[right] = a[left];
			}
		}
		a[left] = partNum;   //将parNum的值再放入其应该在的地方
		for (int l : a) {
			System.out.print(l + " ");
		}
		return left;
	}
	
	
	public static void quickSort(int[] array, int left, int right){
		if(array == null || left >= right){
			return;
		}
		int index = partionTest(array, left, right);
		quickSort(array, left, index - 1);
		quickSort(array, index + 1, right);
	}
	
	public static int partionTest(int[] array, int left, int right){
		if(left > right){
			return left;
		}
		int key = array[right];
		int start = left, end = right - 1;
		while(start <= end){
			while(start <= end && array[start] <= key){
				start++;
			}
			while(start <= end && array[end] > key){
				end--;
			}
			if(start < end){
				MaoPaoSort.swap(array, start, end);
			}
		}
		MaoPaoSort.swap(array, start, right);
		return start;
	}
	
}
